Leetcode |
您所在的位置：网站首页 › leetcode java › Leetcode |
Leetcode
|
链表专题
一、链表简介二、链表基操三、链表做题技巧1.一个原则2.两个考点3.三个注意4.四个技巧
参考文章：
力扣加加-链表专题
一、链表简介
各种数据结构，不管是队列，栈等线性数据结构还是树，图的等非线性数据结构，从根本上底层都是数组和链表。不管你用的是数组还是链表，用的都是计算机内存，物理内存是一个个大小相同的内存单元构成的，如图： val是数据域，用来存放数据，next 则是指向下一个节点的具体对象。 链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。 从上面的物理结构图可以看出数组是一块连续的空间，数组的每一项都是紧密相连的，因此如果要执行插入和删除操作就很麻烦。对数组头部的插入和删除时间复杂度都是
O
(
N
)
O(N)
O(N)，只有对尾部的插入和删除才是
O
(
1
)
O(1)
O(1)，通过计算平均复杂度也是
O
(
N
)
O(N)
O(N)。简单来说“数组对查询特别友好，对删除和添加不友好”。为了解决这个问题，就有了链表这种数据结构。链表适合数据有一定的顺序，并且又需要进行频繁增、删的场景。一个典型的链表逻辑结构图如下： 1.插入 插入只需要考虑要插入位置前驱节点和后继节点（双向链表的情况下需要更新后继节点）即可，其他节点不受影响。因此在给定指针的情况下插入操作的时间复杂度为O(1)。这里给定指针中的指针指的是插入位置的前驱节点。 temp = 待插入位置的前驱节点.next 待插入位置的前驱节点.next = 待插入指针 待插入指针.next = temp如果没有给定指针，我们需要先遍历找到节点，因此最坏情况下时间复杂度为 O(N)。 注意: 考虑头尾指针插入的情况。 2.删除 只需要将需要删除的节点的前驱指针的 next 指针修正为下下个节点即可，注意考虑边界条件。 待删除位置的前驱节点.next = 待删除位置的前驱节点.next.next注意: 考虑头尾指针插入的情况。 3.遍历 遍历比较简单，遍历的伪代码： 当前指针 = 头指针 while(当前节点不为空){ print(当前节点) 当前指针 = 当前指针.next }一个前序遍历的递归的伪代码： dfs(cur) { if 当前节点为空 return print(cur.val) return dfs(cur.next) }4.链表和数组到底有多大的差异? 数组和链表同样作为线性的数组结构，二者在很多方面都是相同的，只是在细微的操作和使用场景上有差异而已，而使用场景，很难在题目中直接考察。因此，对于我们做题来说，二者的差异通常就只是细微的操作差异。 给大家举几个例子，感受一下细微操作的差异。 数组的遍历： for (int i = 0; i 2->3->4->5 dummy.next=head; //初始化pre和end都指向dummy。pre指每次要翻转的链表的头结点的上一个节点。end指每次要翻转的链表的尾节点 ListNode pre=dummy; ListNode end=dummy; while(end.next!=null){ //循环k次，找到需要翻转的链表的结尾,这里每次循环要判断end是否等于空,因为如果为空，end.next会报空指针异常。 //dummy->1->2->3->4->5 若k为2，循环2次，end指向2 for(int i=0;i2 变成2->1。 dummy->2->1 pre.next=reverse(start); //翻转后头节点变到最后。通过.next把断开的链表重新链接。 start.next=next; //将pre换成下次要翻转的链表的头结点的上一个节点。即start pre=start; //翻转结束，将end置为下次要翻转的链表的头结点的上一个节点。即start end=start; } return dummy.next; } //链表翻转 // 例子： head： 1->2->3->4 public ListNode reverse(ListNode head) { //单链表为空或只有一个节点，直接返回原单链表 if (head == null || head.next == null){ return head; } //前一个节点指针 ListNode preNode = null; //当前节点指针 ListNode curNode = head; //下一个节点指针 ListNode nextNode = null; while (curNode != null){ nextNode = curNode.next;//nextNode 指向下一个节点,保存当前节点后面的链表。 curNode.next=preNode;//将当前节点next域指向前一个节点 null |
而数组和链表里的数据虽然用的都是物理内存，都是两者在对物理内存的使用上是非常不一样的，如图： 
数组是连续的内存空间，通常每一个单位的大小也是固定的，因此可以按下标随机访问。而链表则不一定连续，因此其查找只能依靠别的方式，一般我们是通过一个叫 next 指针来遍历查找。链表其实就是一个类。比如一个可能的单链表的定义可以是：
普通链表只有一个后驱节点 next，如果是双向链表还会有一个前驱节点 pre。（实际上链表就是特殊的树，即一叉树）【本文地址】
今日新闻 |
推荐新闻 |